package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * Description: 131. 分割回文串
 *
 * @author weiruibai.vendor
 * Date: 2022/11/16 09:50
 */
public class Solution_131 {
    static Solution_131 instance = new Solution_131();

    public static void main(String[] args) {
        String s = "abcbeffa";
        //s = "aab";
        s = "bb";
        instance.partition(s);
        instance.partition_dp(s);
    }

    /**
     * 可参考Code02_PalindromePartitioningII
     *
     * @param s
     * @return
     */
    public List<List<String>> partition_dp(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        char[] chars = s.toCharArray();
        int N = s.length();
        boolean[][] dp = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            if (i < N - 1) {
                dp[i][i + 1] = chars[i] == chars[i + 1] ? true : false;
            }
            dp[i][i] = true;
        }
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                /**
                 *i...j是否是回文条件：位置i和j相等并且i+1...j-1是回文
                 *
                 */
                dp[i][j] = (dp[i + 1][j - 1] && chars[i] == chars[j]) ? true : false;
            }
        }
        List<String> partRes = new ArrayList<>();
        for (int j = 0; j < N; j++) {
            if (dp[0][j]) {
                calcPartition(s, 0, j, dp, partRes, res);
            }
        }
        System.out.println("dp: \n" + res);
        return res;
    }

    private void calcPartition(String s, int start, int end, boolean[][] dp, List<String> partRes, List<List<String>> res) {
        if (end >= s.length()-1 || start >= s.length() - 1) {
            partRes.add(s.substring(start));
            res.add(new ArrayList<>(partRes));
            partRes.remove(partRes.size() - 1);
            return;
        }
        int e = end;
        partRes.add(s.substring(start, e + 1));
        for (int j = e + 1; j < s.length(); j++) {
            if (dp[e + 1][j]) {
                calcPartition(s, e + 1, j, dp, partRes, res);
            }
        }
        partRes.remove(partRes.size() - 1); // 还原
    }

    /**
     * abcbeffa
     * <p>
     * 1、a b c b e f f a
     * 1、a b c b e ff a
     * 2、a bcb e f f a
     * 3、a bcb e ff a
     * <p>
     * 思路：
     * 1、记录字符的所有回文段起始位置，比如字符
     * - eg：a b c b e f f a
     * 下标：0 1 2 3 4 5 6 7
     * 比如字符a 记录为
     * map{key:'a' value:[{0,0},{7,7}]}
     * map{key:'b' value:[{1,1},{1,3}]}
     * 其中value是个对象，第一个只是回文的开始位置，第二个值是回文的结束位置
     * 2、从第一个字符开始，一次递归，截取（记得还原现场）
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        /**
         * 1、记录字符的所有回文段起始位置，比如字符
         * - eg：a b c b e f f a
         * 下标：0 1 2 3 4 5 6 7
         * 比如字符a 记录为
         * map{key:'a' value:[{0,0},{7,7}]}
         * map{key:'b' value:[{1,1},{1,3}]}
         */
        Map<Character, List<MySegment>> map = buildAllPalindrome(s);
        List<List<String>> res = new ArrayList<>();
        char[] chars = s.toCharArray();
        List<String> partRes = new ArrayList<>();
        /**
         * 2、从第一个字符开始，一次递归，截取（记得还原现场）
         */
        List<MySegment> startSegments = map.get(chars[0]).stream().filter(obj -> obj.start == 0).collect(Collectors.toList());
        for (int i = 0; i < startSegments.size(); i++) {
            calcRestPartition(s, 0, map, startSegments.get(i), partRes, res);
        }
        System.out.println(res);
        return res;
    }

    /**
     * 2、从第一个字符开始，一次递归，截取（记得还原现场）
     *
     * @param s
     * @param curIndex 当前字符串s的下标位置
     * @param map
     * @param segment  s的curIndex位置下字符对应的回文段
     * @param partRes  当前的收集部分
     * @param res      结果
     */
    private void calcRestPartition(String s, int curIndex, Map<Character, List<MySegment>> map, MySegment segment, List<String> partRes, List<List<String>> res) {
        if (curIndex >= s.length() || segment.start == s.length() - 1 || segment.end >= s.length() - 1) {
            partRes.add(s.substring(segment.start));
            res.add(new ArrayList<>(partRes));
            partRes.remove(partRes.size() - 1);
            return;
        }
        int end = segment.end;
        partRes.add(s.substring(segment.start, end + 1));// 回文段
        List<MySegment> mySegments = map.get(s.charAt(end + 1));
        /**
         * 需要过滤
         *- eg ：a b c b e l b f f a
         * 下标：0 1 2 3 4 5 6 7 8 9
         * 比如当前位置到了i=3，但是此时
         * map{key:'b' value:[{1,3},{3,3},{6,6}]}
         * 只需要从当前位置i=3开始就行了，而开始位置1已经遍历过了，不需要重新遍历
         * 也不需要i=6的，因为还没遍历到
         *
         */
        mySegments = mySegments.stream().filter(obj -> obj.start == end + 1).collect(Collectors.toList());
        for (int i = 0; i < mySegments.size(); i++) {
            calcRestPartition(s, end + 1, map, mySegments.get(i), partRes, res);
        }
        partRes.remove(partRes.size() - 1); // 还原
    }

    /**
     * 1、记录字符的所有回文段起始位置
     * - eg：a b c b e f f a
     * 下标：0 1 2 3 4 5 6 7
     * 比如字符a 记录为
     * map{key:'a' value:[{0,0},{7,7}]}
     * map{key:'b' value:[{1,1},{1,3}]}
     * 其中value是个对象，第一个只是回文的开始位置，第二个值是回文的结束位置
     *
     * @param s
     * @return
     */
    private Map<Character, List<MySegment>> buildAllPalindrome(String s) {
        Map<Character, List<MySegment>> ans = new HashMap<>();
        Map<Character, List<Integer>> opMap = new HashMap<>();
        char[] chars = s.toCharArray();
        int N = s.length();
        for (int i = 0; i < N; i++) {
            List<Integer> index = opMap.getOrDefault(chars[i], new ArrayList<>());
            index.add(i);
            opMap.put(chars[i], index);
            MySegment mySegment = new MySegment(i, i);
            List<MySegment> orDefault = ans.getOrDefault(chars[i], new ArrayList<>());
            orDefault.add(mySegment);
            ans.put(chars[i], orDefault);
        }
        for (Map.Entry<Character, List<Integer>> m : opMap.entrySet()) {
            List<Integer> list = m.getValue();
            List<MySegment> mySegments = ans.get(m.getKey());
            int L = list.get(0);
            int R = list.get(0);
            if (list.size() == 1) {
                // 两边扩展
                do {
                    L--;
                    R++;
                } while (L >= 0 && R < N && chars[L] == chars[R]);
                if (L != R && L + 1 != R - 1) {
                    mySegments.add(new MySegment(L + 1, R - 1));
                }
            } else {
                for (int i = 0; i < list.size() - 1; i++) {
                    L = list.get(i);
                    for (int j = i + 1; j < list.size(); j++) {
                        R = list.get(j);
                        int tmpL = L;
                        int tmpR = R;
                        do {
                            tmpL++;
                            tmpR--;
                        } while (tmpL <= tmpR && chars[tmpL] == chars[tmpR]);
                        if (tmpL > tmpR) {
                            mySegments.add(new MySegment(L, R));
                        }
                    }
                }
            }
        }
        return ans;
    }

}

class MySegment {
    public int start; // 回文段开始位置
    public int end;// 回文段结束位置

    public MySegment(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return "MySegment{" +
                "start=" + start +
                ", end=" + end +
                '}';
    }
}
